This invention is related to the field of apparatuses and methods for scheduling the flow of packets. More particularly, it relates to the use of a scheduler for filling voids.
Presently, void filling schedulers utilize only one scheduler operating over the entire set of available wavelengths. (A void is a gap or idle period/pattern of determined time length, appearing at the distribution of packets at the output fields of a switch/router. It essentially represents an absence of packets at the output). Assignment of wavelengths is done in the following manner. Assume that there are N wavelengths available on a certain link. Next, assume that the traffic load per wavelength and traffic overall is xcfx81. In addition, assume that there is one scheduler. The scheduler will schedule use of the packets over all N wavelengths, in effect performing interleaving over all the possible wavelengths. This is depicted in FIG. 1a where it is visible that the scheduler operates over all the wavelengths.
Another example of a void filling scheduler is disclosed in U.S. patent application Ser. No. 09/253,309, Optical Fiber-Delay Line Buffers With Void Filling, filed Feb. 19, 1999 and hereby incorporated by reference. It discloses the use of fiber-delay line buffers that incorporate a void filling procedure.
However, to substantially reduce excess load and increase efficiency using present void filling schedulers, large electronic memories are needed to store large numbers of existing voids ready to be filled. Hence, increased efficiency can only be obtained at the expense of a large increase in the complexity of the void filling scheduling method. In addition, inspecting large number of voids to find out whether a packet can be scheduled in an existing void is very time consuming. Hence, increasing the efficiency entails slowing the speed of the scheduler. Therefore, there is a trade off between complexity and efficiency when using only one scheduler.
The present invention is a method and apparatus for scheduling packets, comprising a plurality of schedulers connected in parallel and a packet divider/classifier circuit operably connected to the plurality of schedulers.
In another embodiment, the invention is an apparatus for scheduling packets, comprising a packet divider/classifier circuit, a plurality of input fibers operably connected to an input of the packet divider/classifier; and a plurality of schedulers connected in parallel. The plurality of schedulers are operably connected to an output of the packet divider/classifier circuit. Furthermore, at least one of the plurality of schedulers comprises at least one buffer. In addition, buffer monitor circuitry is operably connected to the plurality of schedulers. In a preferred embodiment, the buffers are fiber-delay line buffers.
In still another embodiment, the invention comprises a method of asymmetrically allocating bandwidth, comprising the steps of dividing a bandwidth into available wavelengths and assigning the available wavelengths to a plurality of schedulers, wherein at least one of the plurality of schedulers is assigned a different number of wavelengths than another of the plurality of schedulers.
In yet still another embodiment, the invention comprises a method and apparatus of bandwidth grabbing or dynamic bandwidth allocation in which buffer occupancy of at least one of a plurality of schedulers is monitored and at least one packet is redirected to a scheduler having a buffer occupancy below a threshold.